import numpy as np
from plot_path import plot_current_best_path
from perm import opt_path

# 计算两地之间的距离


def get_distance_city(point_position, index, logistics_center_position=None):
    distance = []
    if logistics_center_position == None:
        center_point_x = point_position[index - 1][0]
        center_point_y = point_position[index - 1][1]
        for i in range(len(point_position)):
            center_point_to_other_point = ((center_point_x - point_position[i][0]) ** 2 + (
                center_point_y - point_position[i][1]) ** 2) ** (1/2)
            str_index_format = '{0}->{1}'.format(index, i + 1)
            format_distance = (str_index_format, center_point_to_other_point)
            distance.append(format_distance)
    else:
        for i in range(len(point_position)):
            logistics_center_point_to_city = ((logistics_center_position[0] - point_position[i][0]) ** 2 + (
                logistics_center_position[1] - point_position[i][1]) ** 2) ** (1/2)
            str_index_format = '0->{0}'.format(i + 1)
            format_distance = (
                str_index_format, logistics_center_point_to_city)
            distance.append(format_distance)
    return distance


if __name__ == "__main__":
    # 初始化城市坐标
    points_position = [[12.8, 8.5], [18.4, 3.4], [15.4, 16.6], [18.9, 15.2], [15.5, 11.6], [3.9, 10.6], [10.6, 7.6], [8.6, 8.4], [12.5, 2.1], [
        13.8, 5.2], [6.7, 16.9], [14.8, 2.6], [1.8, 8.7], [17.1, 11], [7.4, 1],  [0.2, 2.8], [11.9, 19.8], [13.2, 15.1], [6.4, 5.6], [9.6, 14.8]]
    # 初始化各个城市需求量
    cities_need_goods = [0.1, 0.4, 1.2, 1.5, 0.8, 1.3, 1.7, 0.6,
                         1.2, 0.4, 0.9, 1.3, 1.3, 1.9, 1.7, 1.1, 1.5, 1.6, 1.7, 1.5]
    cities_distance = []
    # 获得城市之间的距离
    for i in range(1, 21):
        cities_distance.append(get_distance_city(points_position, i))
    # 定义物流中心的坐标
    logistics_center_position = [14.2, 13.1]
    logistics_center_to_cities_distance = get_distance_city(
        points_position, 0, logistics_center_position)

    # 蒙特卡洛
    # 蒙特卡洛模拟的次数
    num_of_monte_carlo = 10000000
    # 初始化城市的路径
    path = np.arange(1, 21)
    current_best_distance = 143.48124943397144
    opt_current_best_distance = 143.48124943397144
    passed_cities = [0 for j in range(20)]
    for _ in range(num_of_monte_carlo):
        # 初始化经过的距离
        distance = 0
        distance_condition = 0
        current_capacity = 0
        num_of_car = 0
        real_path = []
        np.random.shuffle(path)
        # print(path)
        passed_cities = [0 for j in range(20)]
        real_path.append('new car')
        num_of_car += 1
        i = 0
        while i < len(path):
            to_city = path[i]
            return_logistics_center_distance = logistics_center_to_cities_distance[
                to_city - 1][1]
            if real_path[len(real_path) - 1] == 'new car':
                go_to_city_distance = logistics_center_to_cities_distance[to_city - 1][1]
            else:
                go_to_city_distance = cities_distance[path[i -
                                                           1] - 1][to_city - 1][1]
            real_path.append(to_city)
            passed_cities[to_city - 1] = 1
            i += 1
            if distance_condition + go_to_city_distance + return_logistics_center_distance <= 50 and current_capacity + cities_need_goods[to_city - 1] <= 8:
                distance_condition += go_to_city_distance
                current_capacity += cities_need_goods[to_city - 1]
                if np.sum(passed_cities) == 20:
                    distance_condition += return_logistics_center_distance
                    distance += distance_condition
                    break
            else:
                real_path.pop()
                passed_cities[to_city - 1] = 0
                distance_condition += logistics_center_to_cities_distance[real_path[len(
                    real_path) - 1] - 1][1]
                distance += distance_condition
                # 剪枝
                if distance >= current_best_distance:
                    break
                real_path.append('new car')
                num_of_car += 1
                distance_condition = 0
                current_capacity = 0
                i = i - 1
        if distance < current_best_distance and np.sum(passed_cities) == 20:
            print('模拟次数：{0}'.format(_))
            print('找到一条比当前最优路径优化前的一条路径，长度为{0}'.format(distance))
            print('路径为：{0}'.format(real_path))
            plot_current_best_path(real_path, distance)
            current_best_path = []
            current_best_distance = distance
            best_num_of_car = num_of_car
            temp, best_path = opt_path(real_path)
            if temp < opt_current_best_distance:
                opt_current_best_distance = temp
                print('对该路径优化后的路径长度：{0}'.format(opt_current_best_distance))
                for path in best_path:
                    current_best_path.append('new car')
                    for city in path:
                        current_best_path.append(city)
                print('优化后的路径为：{0}'.format(current_best_path))
            else:
                print('优化后的路径长度大于最优的长度：{0}, 路径为：{1}'.format(temp, best_path))

        # if num_of_car <= 5 and np.sum(passed_cities) == 20:
        #     print('所用车辆数：{0}'.format(num_of_car))
        #     print('车辆经过的路径：{0}'.format(real_path))
        #     print('经过的距离：{0}'.format(distance))
    if opt_current_best_distance != 143.48124943397144:
        print('经过{0}次的蒙特卡洛模拟得到的结果：'.format(num_of_monte_carlo))
        print('车辆数：{0}，最优的路径长度：{1}'.format(
            best_num_of_car, opt_current_best_distance))
        print('最优路径为(其中new car代表从物流中心新出发的货车)：{0}'.format(current_best_path))
    else:
        print('没有找更优路径')
    if current_best_distance < 143.48124943397144:
        print('找到一条比使用贪心算法找到路径更优的路径，正在画图')
        plot_current_best_path(current_best_path, opt_current_best_distance)
    else:
        print('没有找到一条比使用贪心算法找到路径更优的路径，正在画图')
        greedy_path = ['new car', 5, 14, 4, 3, 18, 'new car', 1, 7, 8, 19,
                       15, 9, 'new car', 20, 11, 17, 6, 13, 'new car', 10, 12, 2, 16]
        greedy_path_distance = 143.48124943397144
        plot_current_best_path(greedy_path, greedy_path_distance)
